home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / vbdatabs / crc32.cpp < prev    next >
C/C++ Source or Header  |  1999-03-14  |  6KB  |  160 lines
  1. // ------------------------------- //
  2. // -------- Start of File -------- //
  3. // ------------------------------- //
  4. // ----------------------------------------------------------- // 
  5. // C++ Source Code File Name: crc32.cpp 
  6. // Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
  7. // Produced By: Doug Gaer 
  8. // File Creation Date: 08/17/1998 
  9. // Date Last Modified: 03/15/1999
  10. // ----------------------------------------------------------- // 
  11. // ------------- Program description and details ------------- // 
  12. // ----------------------------------------------------------- // 
  13. /*
  14. THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
  15. THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
  16. IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
  17. YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
  18. CORRECTION.
  19.   
  20. The CRC32 functions (Cyclic Redundancy Check) are used to
  21. calculate a sophisticated checksum based on the algebra of
  22. polynomials. The Cyclic Redundancy Check, is a way to detect
  23. bit errors that occur during data storage or transmission.
  24. The CRC-32 algorithm operates on a block of data as a single
  25. large numerical value. The algorithm divides this large value
  26. by the CRC-32 polynomial or generator polynomial, leaving the
  27. remainder 32-bit, which is the checksum. 
  28. */
  29. // ----------------------------------------------------------- // 
  30. #include <iomanip.h>
  31. #include "crc32.h"
  32. #include "crc32tab.h"
  33.  
  34. unsigned long calcCRC32(const char *buf, unsigned len)
  35. // Calculate a 32-bit CRC for a raw pattern of bytes.
  36. // Returns a 32-bit checksum.
  37. {
  38.  unsigned long CRC=0xffffffffL;
  39.  unsigned int n = len;
  40.  
  41.  while(n--) 
  42.    CRC=crc32tab[(CRC ^ (*buf++)) & 0xFF] ^ ((CRC>>8) & 0x00ffffffL);
  43.  
  44.  return CRC ^ 0xffffffffL;
  45. }
  46.  
  47. unsigned long calcCRC32(char *buf, unsigned len)
  48. // Calculate a 32-bit CRC for a raw pattern of bytes.
  49. // Returns a 32-bit checksum.
  50. {
  51.  unsigned long CRC=0xffffffffL;
  52.  unsigned int n = len;
  53.  char *p = (char *)buf;
  54.  while(n--) 
  55.    CRC=crc32tab[(CRC ^ (*p++)) & 0xFF] ^ ((CRC>>8) & 0x00ffffffL);
  56.  
  57.  return CRC ^ 0xffffffffL;
  58. }
  59.  
  60. unsigned long calcCRC32(unsigned char c, unsigned long CRC)
  61. // Calculate a 32-bit CRC table value for a single byte.
  62. // NOTE: The initial CRC value must be set to 0xffffffffL
  63. // and the final 32-bit value that must be XOR'ed with
  64. // 0xffffffffL to obtain the checksum.
  65. {
  66.   unsigned int i;
  67.   i = (unsigned int)c;
  68.   i &= 0xFF; // Reset all the bits
  69.   CRC=crc32tab[(CRC ^ i) & 0xFF] ^ ((CRC>>8) & 0x00ffffffL);
  70.   return CRC;
  71. }
  72.  
  73. unsigned long calcCRC32(fstream &infile)
  74. // Calculate a 32-bit CRC for a file. Assumes the stream
  75. // is already open. Returns a 32-bit checksum.
  76. {
  77.  unsigned long CRC=0xffffffffL;
  78.  unsigned char c;
  79.  unsigned int i;
  80.  
  81.  // Rewind to the start of the stream
  82.  infile.clear(); 
  83.  infile.seekg(0, ios::beg);
  84.  infile.seekp(0, ios::beg);
  85.  
  86.  while(!infile.eof()) {
  87.    infile.get(c);
  88.    i = (unsigned int)c;
  89.    i &= 0xFF; // Reset all the bits
  90.    if(infile.eof()) break;
  91.    CRC=crc32tab[(CRC ^ i) & 0xFF] ^ ((CRC>>8) & 0x00ffffffL);
  92.  }
  93.  return CRC ^ 0xffffffffL;
  94. }
  95.  
  96. int makeCRC32(ostream &stream)
  97. // Write a CRC 32 table for a byte-wise 32-bit CRC calculation
  98. // based on the Autodin/Ethernet/ADCCP polynomial of 0x4C11DB7:
  99. // 0000 0100 1100 0001 0001 1101 1011 0111 (binary) or a poly of
  100. // x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7 +x^5+x^4+x^2+x^1+x^0
  101. // In this representation the coefficient of x^0 is stored in the 
  102. // MSB of the 32-bit word and the coefficient of x^31 is stored in 
  103. // the LSB. Thus 0x4C11DB7 becomes 0xEDB88320:
  104. // 1110 1101 1011 1000 1000 0011 0010 0000 (binary)
  105.  
  106. // Adding the polynomials is performed using an exclusive-or, and
  107. // multiplying a polynomial by x is a right shift by one. If the 
  108. // polynomial is called "p", and each byte is represented as polynomial
  109. // "q", with the lowest power in the most significant bit (so the byte
  110. // 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) 
  111. // mod "p", where "a" mod "b" means the remainder after dividing "a" by
  112. // "b". This calculation is done using the shift-register method of
  113. // multiplying and taking the remainder. The register is initialized
  114. // to zero, and for each incoming bit, x^32 is added mod "p" to the
  115. // register if the bit is a one (where x^32 mod p is p+x^32 = x^26+...+1),
  116. // and the register is multiplied mod "p" by "x" (which is shifting right
  117. // by one and adding x^32 mod "p" if the bit shifted out is a one.) This
  118. // algorithm starts with the highest power (least significant bit) of "q"
  119. // and repeats for all eight bits of "q".
  120. {
  121.   unsigned long c; // CRC shift register 
  122.   unsigned long e; // Polynomial exclusive-or pattern 
  123.   int i;           // Counter for all possible eight bit values 
  124.   int k;           // Byte being shifted into crc apparatus 
  125.  
  126.   // Terms of polynomial defining this crc (except x^32): 
  127.   static const int p[14] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
  128.  
  129.   // Make exclusive-or pattern from polynomial 
  130.   e = 0;
  131.   for (i = 0; i < sizeof(p)/sizeof(int); i++)
  132.     e |= 1L << (31 - p[i]);
  133.  
  134.   // Compute and print table of CRC's, five per line 
  135.   stream << endl;
  136.   stream << "  0x00000000U";
  137.   for (i = 1; i < 256; i++)
  138.   {
  139.     c = 0;
  140.     for (k = i | 256; k != 1; k >>= 1)
  141.     {
  142.       c = c & 1 ? (c >> 1) ^ e : c >> 1;
  143.       if (k & 1)
  144.         c ^= e;
  145.     }
  146.  
  147.     if(i % 5)
  148.       stream << ", 0x" << setfill('0') << setw(8) << hex << c << "U";
  149.     else
  150.       stream << "," << endl << "  0x" << setfill('0') << setw(8) << hex
  151.          << c << "U";
  152.   }
  153.   stream << endl;
  154.   return 1;
  155. }
  156. // ----------------------------------------------------------- // 
  157. // ------------------------------- //
  158. // --------- End of File --------- //
  159. // ------------------------------- //
  160.